'''
@author: Kevin Zhao
@date: Jan 7,2013
@note: Doubly-ended Queue which allows insertion and deletion at both the begin and the end of the queue
'''


'''
Static Double-ended queue implemented with a normal array
Exercise 10.1-5
'''
class ArrayDeque:
    head = 0
    tail = head+1
    current_size=0
    array = []
    def __init__(self, values=None):
        self.array = [0]*values
        
    def insertAtHead(self,x):
        if self.current_size == len(self.array):
            print 'Deque is full'
            return None
        self.array[self.head] = x
        self.head -=1
        if self.head < 0:
            self.head = len(self.array) - 1
        self.current_size +=1
        
    def insertAtTail(self,x):
        if self.current_size == len(self.array):
            print 'deque overflows'
            return None

        self.array[self.tail] = x
        self.tail+=1
        if self.tail > len(self.array) - 1:
            self.tail = 0
        self.current_size +=1

    def deleteAtHead(self):
        if self.current_size ==0:
            print 'deque underflows'
            return None
        self.head += 1
        if self.head > len(self.array) - 1:
            self.head = 0
        result = self.array[self.head]
        self.current_size -=1
        return result 
    def deleteAtTail(self):
        if self.current_size ==0:
            print 'Deque is empty'
            return None
        self.tail -=1
        if self.tail < 0:
            self.tail = len(self.array) - 1
        result = self.array[self.tail]
        if self.tail ==0:#wrapping around
            self.tail = len(self.array)
        self.current_size -=1
        return result
'''
Dynamic Circular Queue implemented with a singly linked list
Exercise 10.2-3
'''
class SinglyLinkdedDeQue:
    head = None
    tail = None
    def enqueue(self, x):
        return
    def dequeue(self):
        return
'''
Static Circular Queue implemented with a doubly linked list
'''
class DoublyLinkedDeQue:
    head = None
    tail = None
    def enqueue(self, x):
        return
    def dequeue(self):
        return
